/*
 * bst/node.hh - Plain node implementation.
 * Copyright (C) 2008  Mikhail Vorozhtsov
 * See the LICENSE section of the README file for details.
 */

/* $Id$ */

#ifndef HEADER_LIBBST_MJ_NODE_HH
#define HEADER_LIBBST_MJ_NODE_HH

#include HEADER (LIBBST_PREFIX,base.hh)

START_NAMESPACE (LIBBST_NS)

template <typename T, class P = T, u64_t OFFSET = 0,
          typename CMP = compare<T, T> >
class node_t : public base_node_t<T, P, OFFSET, CMP>
{
private:
  typedef base_node_t<T, P, OFFSET, CMP> parent_t;

public:
  __LIBBST_MJ_NODE_WRAPPERS
  __LIBBST_MJ_NODE_ORD_PREV
  __LIBBST_MJ_NODE_ORD_NEXT

public:
  template <typename TREE>
  node_t *
  get_parent (TREE *tree UNUSED, node_t *top) const
  {
    const T *x = this->to_container ();
    node_t *n = top, *parent = NULL;

    while (true)
      {
        if (n == this)
          return parent;

        const T *t = n->to_container ();
        parent = n;

        if (CMP::less_p (*t, *x))
          n = n->get_right ();
        else
          n = n->get_left ();
      }
  }

  template <typename TREE>
  void
  insert (TREE *tree, node_t *parent, bool left_p, node_t *prev_or_next UNUSED)
  {
    if (parent)
      {
        if (left_p)
          parent->set_left (this);
        else
          parent->set_right (this);
      }
    else
      tree->set_root (this);

    this->set_left (NULL);
    this->set_right (NULL);
  }

  template <typename TREE>
  void
  remove (TREE *tree, node_t *parent, bool left_p, node_t *prev_or_next UNUSED)
  {
    if (parent)
      {
        if (left_p)
          parent->set_left (NULL);
        else
          parent->set_right (NULL);
      }
    else
      tree->set_root (NULL);
  }

  template <typename TREE>
  node_t *
  replace_with_pred (TREE *tree, node_t *parent, bool left_p, node_t *pred,
                     node_t *pred_parent, node_t *&succ UNUSED)
  {
    node_t *left = ((node_t *) this)->get_left ();
    node_t *right = ((node_t *) this)->get_right ();
    node_t *pred_left = pred->get_left ();

    pred->set_right (right);

    if (pred_parent != this)
      {
        pred->set_left (left);
        pred_parent->set_right (pred_left);
      }

    if (parent)
      {
        if (left_p)
          parent->set_left (pred);
        else
          parent->set_right (pred);
      }
    else
      tree->set_root (pred);

    return pred_left;
  }

  template <typename TREE>
  node_t *
  replace_with_succ (TREE *tree, node_t *parent, bool left_p, node_t *succ,
                     node_t *succ_parent, node_t *prev_or_next UNUSED)
  {
    node_t *left = ((node_t *) this)->get_left ();
    node_t *right = ((node_t *) this)->get_right ();
    node_t *succ_right = succ->get_right ();

    succ->set_left (left);

    if (succ_parent != this)
      {
        succ->set_right (right);
        succ_parent->set_left (succ_right);
      }

    if (parent)
      {
        if (left_p)
          parent->set_left (succ);
        else
          parent->set_right (succ);
      }
    else
      tree->set_root (succ);

    return succ_right;
  }

  template <typename TREE>
  node_t *
  rotate_left (TREE *tree, node_t *parent)
  {
    node_t *pivot = ((node_t *) this)->get_right ();
    node_t *pivot_left = pivot->get_left ();

    pivot->set_left (this);
    this->set_right (pivot_left);

    if (parent)
      {
        if (this == parent->get_left ())
          parent->set_left (pivot);
        else
          parent->set_right (pivot);
      }
    else
      tree->set_root (pivot);

    return pivot;
  }

  template <typename TREE>
  node_t *
  rotate_right (TREE *tree, node_t *parent)
  {
    node_t *pivot = ((node_t *) this)->get_left ();
    node_t *pivot_right = pivot->get_right ();

    pivot->set_right (this);
    this->set_left (pivot_right);

    if (parent)
      {
        if (this == parent->get_left ())
          parent->set_left (pivot);
        else
          parent->set_right (pivot);
      }
    else
      tree->set_root (pivot);

    return pivot;
  }

  template <typename TREE>
  void
  replace (TREE *tree, node_t *with)
  {
    node_t *parent = this->get_parent (tree, tree->get_root ());

    if (parent)
      {
        if (parent->get_left () == this)
          parent->set_left (with);
        else
          parent->set_right (with);
      }
    else
      tree->set_root (with);

    with->set_left (this->get_left ());
    with->set_right (this->get_right ());
  }
};

END_NAMESPACE

#endif /* HEADER_LIBBST_MJ_NODE_HH */

